#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 20
#define TElemType char

//孩子表示法
typedef struct CTNode {
    //链表中每个结点存储的不是数据本身，而是数据在数组中存储的位置下标
    int child;
    struct CTNode * next;
}ChildPtr;

typedef struct {
    //结点的数据类型
    TElemType data;
    //孩子链表的头指针
    ChildPtr * firstChild;
}CTBox;

typedef struct {
    //存储结点的数组
    CTBox nodes[MAX_SIZE];
    //结点数量和树根的位置
    int num, root;
}CTree;

//孩子表示法存储普通树
CTree initTree(CTree tree) {
    tree.num = 10;
    tree.nodes[0].data = 'R';
    tree.nodes[1].data = 'A';
    tree.nodes[2].data = 'B';
    tree.nodes[3].data = 'C';
    tree.nodes[4].data = 'D';
    tree.nodes[5].data = 'E';
    tree.nodes[6].data = 'F';
    tree.nodes[7].data = 'G';
    tree.nodes[8].data = 'H';
    tree.nodes[9].data = 'I';
    //所有节点顺序表初始化
    for(int i = 0; i < tree.num; i++) {
        tree.nodes[i].firstChild = (ChildPtr *)malloc(sizeof(ChildPtr));
        tree.nodes[i].firstChild->next = NULL;
    }
    //节点0的孩子节点的链表初始化
    ChildPtr * p0 = tree.nodes[0].firstChild;
    for(int j0 = 1; j0 < 4; j0++) {
        ChildPtr * newElem = (ChildPtr *)malloc(sizeof(ChildPtr));
        newElem->next = NULL;
        newElem->child = j0;
        p0->next = newElem;
        p0 = p0->next;
    }
    //节点1的孩子节点的链表初始化
    ChildPtr * p1 = tree.nodes[1].firstChild;
    for(int j1 = 4; j1 < 6; j1++) {
        ChildPtr * newElem = (ChildPtr *)malloc(sizeof(ChildPtr));
        newElem->next = NULL;
        newElem->child = j1;
        p1->next = newElem;
        p1 = p1->next;
    }
    //节点3的孩子节点的链表初始化
    ChildPtr * p3 = tree.nodes[3].firstChild;
    for(int j3 = 6; j3 < 7; j3++) {
        ChildPtr * newElem = (ChildPtr *)malloc(sizeof(ChildPtr));
        newElem->next = NULL;
        newElem->child = j3;
        p3->next = newElem;
        p3 = p3->next;
    }
    //节点6的孩子节点的链表初始化
    ChildPtr * p6 = tree.nodes[6].firstChild;
    for(int j6 = 7; j6 < 10; j6++) {
        ChildPtr * newElem = (ChildPtr *)malloc(sizeof(ChildPtr));
        newElem->next = NULL;
        newElem->child = j6;
        p6->next = newElem;
        p6 = p6->next;
    }

    return tree;

}

void findKids(CTree tree) {
    char a;
    int isFind = 0;
    printf("请输入要查询的节点值：R或A~I\n");
    scanf("%c", &a);
    for (int i = 0; i < tree.num; i++) {
        if(tree.nodes[i].data == a) {
            ChildPtr * p = tree.nodes[i].firstChild->next;
            while (p)
            {
                /* code */
                isFind = 1;
                printf("%c ", tree.nodes[p->child].data);
                p = p->next;
            }
            break;
        }
    }
    if(isFind == 0) {
        printf("此节点为叶子节点");
    }
}

int main(int argc, char * argv[]) {
    CTree tree;
    //初始化树
    for(int i = 0; i < MAX_SIZE; i++) {
        tree.nodes[i].data = " ";
        tree.nodes[i].firstChild = NULL;
    }
    tree = initTree(tree);
    tree.root = 0;
    printf("树的孩子表示法: \n");
    for(int j = 0; j < tree.num; j++) {
        printf("%c ", tree.nodes[j].data);
        ChildPtr * p = tree.nodes[j].firstChild->next;
        while(p) {
            printf("%d ", p->child);
            p = p->next;
        }
        printf("\n");
    }
    findKids(tree);

    return 0;
}